package com.kobeliu.entity;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 剑指 26
 *
 *
 */

public class Demo_41_No26 {

    public static void main(String[] args) {

        Demo_39_sword_32.TreeNode treeNodeA = new Demo_39_sword_32.TreeNode(4);
        treeNodeA.left = new Demo_39_sword_32.TreeNode(2);
        treeNodeA.right = new Demo_39_sword_32.TreeNode(3);
        treeNodeA.left.left = new Demo_39_sword_32.TreeNode(4);
        treeNodeA.left.right = new Demo_39_sword_32.TreeNode(5);
        treeNodeA.right.left = new Demo_39_sword_32.TreeNode(6);
        treeNodeA.right.right = new Demo_39_sword_32.TreeNode(7);
        treeNodeA.left.left.left = new Demo_39_sword_32.TreeNode(8);
        treeNodeA.left.left.right = new Demo_39_sword_32.TreeNode(9);

        Demo_39_sword_32.TreeNode treeNodeB = new Demo_39_sword_32.TreeNode(4);
        treeNodeB.left = new Demo_39_sword_32.TreeNode(8);
        treeNodeB.right = new Demo_39_sword_32.TreeNode(9);

        System.out.println(isSubStructure(treeNodeA,treeNodeB));


    }

    private static boolean isSubStructure(Demo_39_sword_32.TreeNode treeNodeA, Demo_39_sword_32.TreeNode treeNodeB) {
        return false;
    }

    /**
     * 写了1个小时 写了个双5% 我可真是个大傻吊
     * @param A
     * @param B
     * @return
     */
    public static boolean isSubStructure1(Demo_39_sword_32.TreeNode A, Demo_39_sword_32.TreeNode B) {

        if(A==null || B==null) return false;
        Queue<Demo_39_sword_32.TreeNode> queue = new LinkedList<>();  //层序遍历树A，BFS广度优先
        Queue<Demo_39_sword_32.TreeNode> queueA = new LinkedList<>(); //遍历A的子树
        Queue<Demo_39_sword_32.TreeNode> queueB = new LinkedList<>(); //遍历B的子树

        queue.add(A); //头节点入队
        Demo_39_sword_32.TreeNode temp;
        Demo_39_sword_32.TreeNode tempA;
        Demo_39_sword_32.TreeNode tempB;
        boolean flag = true;

        while(queue.size()>0){
            temp = queue.poll();
            if(temp.val == B.val){
                queueA.clear();
                queueB.clear();
                flag = true;
                queueA.add(temp);
                queueB.add(B);
                while(queueA.size()>0 && queueB.size()>0 && flag){
                    tempA = queueA.poll();
                    tempB = queueB.poll();
                    if(tempA.val == tempB.val){
                        if(tempA.left!=null) queueA.add(tempA.left);
                        if(tempA.right!=null) queueA.add(tempA.right);
                        if(tempB.left!=null) queueB.add(tempB.left);
                        if(tempB.right!=null) queueB.add(tempB.right);
                    }else{
                        flag = false;
                    }
                }
                //出来的时候，两个数组都是空的 代表为true；
                if(queueB.size()==0){
                    return true;
                }
            }
            if(temp.left!=null) queue.add(temp.left);
            if(temp.right!=null) queue.add(temp.right);
        }
        return false;
    }




}
